package offerbook;

/**
 *  在行列都排好序的矩阵中找数
 *      【题目】 给定一个有N*M的整型矩阵matrix和一个整数K，
 *             matrix的每一行和每一 列都是排好序的【假设从小到大】。 实现一个函数，
 *             判断K是否在matrix中。
 *     【要求】 时间复杂度为O(N+M)， 额外空间复杂度为O(1)
 *         分析：遍历肯定不行，运用数据状况，因为行和列都是排好序的，那么从这个条件出发
 *         方式1: 从最后一列第一个数开始，若这个数大于target，那么直接往前移动一列，
 *                 否则开始遍历该列，在遍历过程中，如果遇到元素比target大，
 *                 那么直接往前移动列【行不变，不用归0，画图】
 *         方式2：从最后一行的第一个数开始，道理同方式1
 * @date 2020/3/7 22:15
 */
public class Code03_FindTargetInMatrix {
    public static boolean hasTarget(int[][]m,int target){
        if(m == null || m.length == 0 || m[0].length == 0) return false;
        int curCol = m[0].length - 1;
        int curRow = 0;
        while (curCol >= 0 && curRow <= m.length - 1){
            if(target < m[curRow][curCol]){
                curCol --;
            }else if(target > m[curRow][curCol]){
                curRow ++;
            }else {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] matrix = new int[][] { { 0, 1, 2, 3, 4, 5, 6 },// 0
                { 10, 12, 13, 15, 16, 17, 18 },// 1
                { 23, 24, 25, 26, 27, 28, 29 },// 2
                { 44, 45, 46, 47, 48, 49, 50 },// 3
                { 65, 66, 67, 68, 69, 70, 71 },// 4
                { 96, 97, 98, 99, 100, 111, 122 },// 5
                { 166, 176, 186, 187, 190, 195, 200 },// 6
                { 233, 243, 321, 341, 356, 370, 380 } // 7
        };
        int K = 233;
        System.out.println(hasTarget(matrix, K));
    }

    /**
     * 统计一个数字在排序数组中出现的次数。
     * 比较优的算法肯定是O(logn)级别的。
     * 原题在leetcode34
     * @date 2020/3/11 14:55
     */
    public static class Code38_GetNumberOfKInSortArray {
        public static void main(String[] args) {
            int[]arr = {1,2,3,3,3,3,5,6};
            System.out.println(GetNumberOfK(arr, 4));

        }
        //方式1：遍历O(n)级别，略
        //方式2：二分查找
        public static int[] GetNumberOfK(int [] arr , int k) {
            if(arr == null || arr.length == 0) return new int[]{-1,-1};
            if(k < arr[0] || k > arr[arr.length-1]) return new int[]{-1,-1};
            return find(arr,k);
        }

        /**
         * 二分查找
         * @param arr
         * @param k
         * @return
         */
        private static int[] find(int[] arr, int k) {
            int left = 0;
            int right = arr.length - 1;
            int mid = left + (right - left)/2;
            while (left <= right){
                if(arr[mid] > k){
                    right = mid -1;
                }else if(arr[mid] < k) {
                    left = mid + 1;
                }else {
                    break;
                }
                mid = left + (right - left)/2;
            }
            //没找到
            if(left > right) return new int[]{-1,-1};
            //先找到对应target的index，然后分别去左边和右边查找
            int startIndex = findLeft(arr,k,mid);
            int endIndex = findRight(arr,k,mid);
            return new int[]{startIndex,endIndex};
        }
        //左侧查找，all the elements  <= k
        private static int findLeft(int[] arr, int k, int end) {
            // assert all the elements <= k and must has k
            int left = 0;
            int right = end;
            int mid = left + (right - left)/2;
            while (left <= right){
                //如果mid == k，判断mid 的前一个位置是否还是k，若是right = mid - 1
                if(arr[mid] == k){
                    if(mid == 0) return 0;
                    if(arr[mid] != arr[mid-1]) return mid;
                    right = mid - 1;
                }else if(arr[mid] < k){
                    left = mid + 1;
                }
                mid = left + (right - left)/2;
            }
            //never can reach here
            return -1;
        }
        private static int findRight(int[] arr, int k, int start) {
            //assert all the elements  >= k and must has k
            int left = start;
            int right = arr.length-1;
            int mid = left + (right - left)/2;
            while (left <= right){
                //如果mid == k，判断mid 的后一个位置是否还是k，若是left = mid + 1
                if(arr[mid] == k){
                    if(mid == arr.length - 1) return arr.length - 1;
                    if(arr[mid] != arr[mid + 1]) return mid;
                    left = mid + 1;
                }else if(arr[mid] > k){
                    right = mid - 1;
                }
                mid = left + (right - left)/2;
            }
            //never can reach here
            return -1;
        }


    }
}
